\documentclass[a4paper, 12pt]{article}


\usepackage[francais]{babel}	% Langue
\usepackage[utf8]{inputenc}	% Encodage du texte
\usepackage[T1]{fontenc}		% Encodage de police
\usepackage{lmodern}			% Police

%\usepackage{textcomp}		% Symboles
%\usepackage{url}			% URLs
\usepackage{graphicx}		% Images
%\usepackage[empty]{fullpage}	% Pleine page
%\usepackage{nopageno}		% Pagination
%\usepackage{multirow}		% Tableau complexe
\usepackage{caption}
\usepackage{array}


\title{TP MOIA\\Algorithmique Génétique}
\author{\bsc{Boujedli} Najim \and \bsc{Paneri} Jérémy}
\date{Master 1 Informatique\\ 2012 -- 2013}

\begin{document}
\maketitle

\begin{figure}[!b]
   \centering\includegraphics[scale=0.2]{ufc.png}
\end{figure}

\thispagestyle{empty}
\newpage


% CONTENU %


\section{Modélisation}

\subsection{Codage}

La modélisation d'un individu se fait via un tableau de bits, dont la taille reste à déterminer. Nous savons que le diamètre de chaque cercle doit être au moins égal à 10, et que la somme des trois ne doit pas dépasser 100. Nous avons donc $b_{min}=10$ et $b_{max}=100-10-10=80$. On nous impose également la précision, qui est de $0{,}1$.



\begin{center}
	$\begin{array}{ccc}
	
		n_{bit}	&	=	&	\left\lceil \log_2 \left( \frac{b_{max}-b_{min}}{precision} \right) \right\rceil\\
					&	=	&	\left\lceil \log_2 \left( \frac{80-10}{0{,}1} \right) \right\rceil\\
					&	=	&	\left\lceil \log_2 \left( \frac{70}{0{,}1} \right) \right\rceil\\
					&	=	&	\left\lceil \log_2 \left( 700 \right) \right\rceil\\
					&	\approx	&	\left\lceil 9{,}451211 \right\rceil\\
					&	=	&	10
						
	\end{array}$
\end{center}

Pour un seul diamètre, nous avons donc besoin de 10 bits. Avec un peu de réflexion, on se rend compte que le troisième peut être déduit des deux premiers : nous n'en représenterons donc que deux, avec un tableau de 20 bits en tout.

\begin{table}[h]
\begin{center}
\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
	\hline
	0&1&1&0&1&0&1&1&1&0&0&1&0&1&1&0&1&0&0&1\\
	\hline
\end{tabular}
\caption{Gènes d'un individu lambda}
\end{center}
\end{table}





\subsection{Décodage}


Pour décoder un individu, c'est-à-dire trouver la valeur des deux diamètres le composant, nous considérons séparément les deux parties de son gène (de 10 bits chacun).


\begin{center}
	$\begin{array}{ccc}
	
		diametre	&	=	&	\sum\limits_{i=0}^{n_{bit}} \left( \frac{b_{max}-b_{min}}{2^{n_{bit}}}*bit_i*2^i \right)\\
					&	=	&	\sum\limits_{i=0}^{10} \left( \frac{80-10}{2^{10}}*bit_i*2^i \right)\\
					&	=	&	\sum\limits_{i=0}^{10} \left( \frac{70}{1024}*bit_i*2^i \right)
					
	\end{array}$
\end{center}


Chaque moitié nous donnera la valeur d'un des diamètres ; il nous restera alors simplement à déduire la valeur du troisième grâce à la formule $d_3 = D - d_1 - d_2$.



\subsection{Fitness}

La caractéristique qui nous intéresse ici est la surface restante du cercle principal, que l'on cherche la plus grande possible. Le calcul d'une surface impliquant $\pi$, nous pouvons en faire abstraction lors du calcul du fitness : c'est le rapport entre les individus qui nous intéresse, et non la surface de manière exacte.

\begin{center}
	$\begin{array}{ccc}
	
		surface	&	=	&	\pi R^2 - \left( \pi r_1^2 + \pi r_2^2 + \pi r_3^2 \right)\\
					&	=	&	\pi \left(\frac{D}{2}\right)^2 - \left( \pi \left(\frac{d_1}{2}\right)^2 + \pi \left(\frac{d_2}{2}\right)^2 + \pi \left(\frac{d_3}{2}\right)^2 \right)\\
					&	=	&	\frac{\pi D^2}{4} - \left( \frac{\pi d_1^2}{4} + \frac{\pi d_2^2}{4} + \frac{\pi d_3^2}{4} \right)\\
					&	=	&	\frac{\pi}{4} \left(D^2 - d_1^2 - d_2^2 - d_3^2 \right)\\
					&	=	&	\frac{\pi}{4} * fitness
					
	\end{array}$
\end{center}


Ceci économise simplement des calculs d'un point de vue machine. Une fois les itérations terminées, il suffira donc de multiplier le fitness du meilleur individu par $\frac{\pi}{4}$ pour obtenir la surface recherchée.






\section{Plan expérimental}


\subsection{Taille de la population}


\begin{center}
\begin{tabular}{|>\bf c|c|c|c|>\it c|>\it c|}
	\hline
	Population	&	 Mutation	&	 Croisement	&	Itérations	&	 Meilleur f.	&	F. moyen\\
	\hline
	
2	&	0.015	&	0.5	&	10	&	5908.42	&	5900.96\\
4	&	0.015	&	0.5	&	10	&	6635.12	&	6457.83\\
8	&	0.015	&	0.5	&	10	&	6316.98	&	5341.11\\
16	&	0.015	&	0.5	&	10	&	6505.14	&	5738.32\\
32	&	0.015	&	0.5	&	10	&	6649.82	&	5443.11\\
64	&	0.015	&	0.5	&	10	&	6655.82	&	5684.69\\
128	&	0.015	&	0.5	&	10	&	6665.28	&	5603.44\\
256	&	0.015	&	0.5	&	10	&	6666.16	&	5750.90\\
512	&	0.015	&	0.5	&	10	&	6663.62	&	5608.93\\
1024	&	0.015	&	0.5	&	10	&	6663.86	&	5621.22\\

	\hline
\end{tabular}
\end{center}



\subsection{Taux de mutation}

\begin{center}
\begin{tabular}{|c|>\bf c|c|c|>\it c|>\it c|}
	\hline
	Population	&	 Mutation	&	 Croisement	&	Itérations	&	 Meilleur f.	&	F. moyen\\
	\hline
	
10	&	0.01	&	0.5	&	10	&	6525.52 & 5375.47\\
10	&	0.11	&	0.5	&	10	&	6638.98 & 6082.28\\
10	&	0.21	&	0.5	&	10	&	6441.5 & 4293.02\\
10	&	0.31	&	0.5	&	10	&	6524.42 & 5269.20\\
10	&	0.41	&	0.5	&	10	&	6598.08 & 5448.53\\
10	&	0.51	&	0.5	&	10	&	6612.58 & 5596.96\\
10	&	0.61	&	0.5	&	10	&	6603.98 & 5568.89\\
10	&	0.71	&	0.5	&	10	&	6386.18 & 5686.62\\
10	&	0.81	&	0.5	&	10	&	6426.54 & 5177.71\\
10	&	0.91	&	0.5	&	10	&	6288.88 & 4906.46\\

	\hline
\end{tabular}
\end{center}




\subsection{Taux de croisement}


\begin{center}
\begin{tabular}{|c|c|>\bf c|c|>\it c|>\it c|}
	\hline
	Population	&	 Mutation	&	 Croisement	&	Itérations	&	 Meilleur f.	&	F. moyen\\
	\hline
	
10	&	0.015	&	0.1	&	10	&	6463.33 & 6463.33\\
10	&	0.015	&	0.2	&	10	&	6061.18 & 6059.21\\
10	&	0.015	&	0.3	&	10	&	6645.76 & 6643.07\\
10	&	0.015	&	0.4	&	10	&	6666.32 & 6666.31\\
10	&	0.015	&	0.5	&	10	&	6657.18 & 6652.48\\
10	&	0.015	&	0.6	&	10	&	6585.42 & 6090.07\\
10	&	0.015	&	0.7	&	10	&	6470.08 & 6359.53\\
10	&	0.015	&	0.8	&	10	&	6658.0 & 6658.0\\
10	&	0.015	&	0.9	&	10	&	6619.92 & 6607.53\\
10	&	0.015	&	1.0	&	10	&	6585.02 & 6503.19\\

	\hline
\end{tabular}
\end{center}



\subsection{Nombre d'itérations}


\begin{center}
\begin{tabular}{|c|c|c|>\bf c|>\it c|>\it c|}
	\hline
	Population	&	 Mutation	&	 Croisement	&	Itérations	&	 Meilleur f.	&	F. moyen\\
	\hline
	
10	&	0.015	&	0.5	&	1	&	6630.18 & 5810.36\\
10	&	0.015	&	0.5	&	2	&	6554.94 & 6230.97\\
10	&	0.015	&	0.5	&	3	&	6636.55 & 6619.00\\
10	&	0.015	&	0.5	&	4	&	6516.34 & 6512.42\\
10	&	0.015	&	0.5	&	5	&	6588.98 & 6547.17\\
10	&	0.015	&	0.5	&	6	&	6638.42 & 6636.48\\
10	&	0.015	&	0.5	&	7	&	6573.82 & 6573.81\\
10	&	0.015	&	0.5	&	8	&	6625.04 & 6624.75\\
10	&	0.015	&	0.5	&	9	&	6527.45 & 6525.64\\
10	&	0.015	&	0.5	&	10	&	6647.92 & 6606.29\\

	\hline
\end{tabular}
\end{center}




\subsection{Bilan}


\begin{description}
	\item[Population :] Influe moyennement sur le résultat. \textit{$\sim$100}
	\item[Mutation :] Influe grandement sur le résultat. \textit{$\sim$0.1}
	\item[Croisement :] Influe faiblement sur le résultat. \textit{$\sim$0.5}
	\item[Itérations :] Influe moyennement sur le résultat. \textit{$\sim$10}
\end{description}

Le meilleur individu jamais obtenu a un fitness de 6666,66 (pour une surface de 5235,98) ; avec les trois diamètres valant 33,3, 33,3 et 33,4.




\end{document}
